# -*- coding: utf-8 -*-
"""
@author:  yinbing.li(yinbing.li@zillnk.com)
@version: 1.0.0
@file:    leetcode_剑指OfferII098_路径的数目.py
@time:    2023/4/14 11:24
"""
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        dp = [[0] * n for _ in range(m)]
        dp[0][1] = 1
        dp[1][0] = 1
        for i in range(m):
            for j in range(n):
                dp[i][j] = 1 if i == 0 or j == 0 else dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]


s = Solution()
print(s.uniquePaths(3, 7))